This application claims priority from Japanese patent application number 11-302088, filed Oct. 25, 1999, which is hereby incorporated herein by reference in its entirety.
1. Field of the Invention
The present invention relates to a priority encoder and an encoding method using the priority encoder, and more particularly to a compact and high-speed priority encoder and a high-speed encoding method.
2. Description of Related Art
The function of a priority encoder is to output a code corresponding to the highest-priority input line among a plurality of input lines having a true value when input signal is input to more than one of input lines which are prioritized and given codes. FIG. 13 shows an example of a prior encoder and FIG. 14 is a truth table showing inputs and outputs of the priority encoder shown in FIG. 13. In the priority encoder 100 (all the inputs are negative logic) shown in FIG. 13, when more than one of eight data inputs (IN7N, IN6N, IN5N, IN4N, IN3N, IN2N, IN1N, and IN0N) are simultaneously activated (xe2x80x9c0xe2x80x9d), a 3-bit code (binary code) representing the input having the highest priority among the activated inputs (this input will be hereinafter referred to as xe2x80x9chighest-priority inputxe2x80x9d) is output. As shown in FIG. 13, this code is generated by combining input signals and their inverted signals.
The input IN7N has the highest priority. The smaller the number t in INtN is, the lower the priority is. In this example, the highest-priority input is determined with respect to an active input (xe2x80x9c0xe2x80x9d). As shown in FIG. 14, when the input IN7N having the highest priority has the highest-priority true input, the output signals (xe2x80x9cA2 A1 A0xe2x80x9d) of the encoder 100 are xe2x80x9c0 0 0xe2x80x9d, and when the input IN0N having the lowest priority has the highest-priority true input, the output signals are xe2x80x9c1 1 1xe2x80x9d. Thus, the output signals are signals in which a binary code corresponding to the number t of INtN is inverted. The mark xe2x80x9cxe2x88x92xe2x80x9d in FIG. 14 denotes xe2x80x9cdon""t carexe2x80x9d. An output GS is a signal representing the presence or absence of active input signals into the encoder 100. An input EI and an output EO are signals for expansion, and the output EO is connected to the input EI of the next-stage encoder.
FIG. 15(a) shows another example of a priority encoder and FIG. 15(b) is a truth table showing inputs and outputs of the priority encoder shown in FIG. 15(a). A priority encoder 110 shown in FIG. 15(a) comprises a selector circuit 116 and a plurality of priority encoders 112 and 114. FIG. 16(a) shows an example of a 4-to-2 priority encoder 112, and FIG. 16(b) is a truth table showing inputs and outputs of the priority encoder 112 shown in FIG. 16(a). FIG. 17 shows an example of the selector circuit 116. Unlike the priority encoder 100 shown in FIG. 13 and its inputs and outputs shown in FIG. 14, the input IN0N has the highest priority in the priority encoder 110. The larger the number t in INtN is, the lower the priority is. As shown in FIG. 15(b), when the input IN0N having the highest priority has the highest-priority true input, the output signals (xe2x80x9cA2 A1 A0xe2x80x9d) of the encoder 110 are xe2x80x9c0 0 0xe2x80x9d, and when the input IN7N having the lowest priority has the highest-priority true input, the output signals are xe2x80x9c1 1 1xe2x80x9d. Thus, the output signals are represented in binary notation, indicating the number t in INtN of the highest-priority input having a true value.
Eight data inputs (IN0N, IN1N, IN2N, IN3N, IN4N, IN5N, IN6N, and IN7N) are divided into two groups, namely a group of four higher-priority inputs (IN0N, IN1N, IN2N, and IN3N) and a group of four lower-priority inputs (IN4N, IN5N, IN6N, and IN7N). The 4-to-2 priority encoders 112 and 114 receives these two groups of inputs, respectively. The encoders 112 and 114 each output a 2-bit binary code representing the active highest-priority input of the four inputs. The selector circuit 116 outputs lower-order 2 bits (xe2x80x9cA1 A0xe2x80x9d) of the output signals (xe2x80x9cA2 A1 A0xe2x80x9d) in response to the output from the higher encoder 112.
By combination of a selector circuit and a plurality of priority encoders, and by expanding the input and output of the selector circuit, the priority encoder can be configured as a greater whole encoder, for example, a 64-to-6 priority encoder 120, by using four 16-to-4 priority encoders 122, as shown in FIG. 18. However, since the priority encoder contains a number of components as shown in FIG. 13, a combination of a plurality of priority encoders as shown in FIG. 18 increases the number of components in the greater whole encoder, which leads to the increase in the circuit size of the greater whole encoder, the increase in the number of circuit stages, and the reduction of processing speed.
Objects of the present invention are to downsize the priority encoder by reducing the number of components and to achieve a high-speed encoding.
The priority encoder of the present invention comprises:
higher-order-bit encoding means for outputting a higher-order m-bit code corresponding to the group having the highest priority among those groups out of 2m groups distinguished by higher-order m bits to which true values are input (hereinafter referred to as xe2x80x9chighest-priority group distinguished by the higher-order m bitsxe2x80x9d); each of the 2m groups consisting of 2n input lines having common higher-order m bits of (m+n)-bit output code; and
lower-order-bit encoding means for outputting a lower-order n-bit code corresponding to the input line having the highest priority among input lines to which true values are input; the input lines being part of 2n input lines which make up the highest-priority group distinguished by the higher-order m bits and which are distinguished by the lower n bits of the (m+n)-bit output code.
An encoding method using the priority encoder of the present invention comprises the steps of:
outputting higher-order bits corresponding to the group having the highest priority among those groups distinguished by higher-order bits to which true values are input (hereinafter referred to as xe2x80x9chighest-priority group distinguished by the higher-order bitsxe2x80x9d); each of the groups distinguished by higher-order bits comprising input lines which are grouped on the basis of higher-order bits of the code; and
outputting lower-order bits corresponding to the input line having the highest priority among input lines to which true values are input; the input lines being part of input lines which make up the highest-priority group distinguished by the higher-order bits and are distinguished by the lower bits of the output code.